首页 > 试题广场 >

二叉树的镜像

[编程题]二叉树的镜像
  • 热度指数：133762 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
操作给定的二叉树，将其变换为源二叉树的镜像。
数据范围：二叉树的节点数 ， 二叉树每个节点的值
要求： 空间复杂度 。本题也有原地操作，即空间复杂度 的解法，时间复杂度

比如：
源二叉树
镜像二叉树

示例1

输入

{8,6,10,5,7,9,11}

输出

{8,10,6,11,9,7,5}

说明

如题面所示
示例2

输入

{}

输出

{}

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
Python 3
wongself头像 wongself 
class Solution:
    def Mirror(self , pRoot: TreeNode) -> TreeNode:
        if not pRoot&nbs***bsp;(not pRoot.left and not pRoot.right):
            return pRoot
        pRoot.left, pRoot.right = self.Mirror(pRoot.right), self.Mirror(pRoot.left)
        return pRoot


发表于 2022-08-21 13:28:44 回复(0)
Python 3
来个offer叭！头像 来个offer叭！ 
class Solution:
    def Mirror(self , pRoot: TreeNode) -> TreeNode:
        if not pRoot:
            return pRoot
        pRoot.left ,pRoot.right = pRoot.right, pRoot.left
        self.Mirror(pRoot.left)
        self.Mirror(pRoot.right)
        return pRoot

发表于 2022-07-21 19:33:54 回复(0)
Python 3
寒塘渡鹤影X头像 寒塘渡鹤影X 
class Solution:
    def Mirror(self , pRoot: TreeNode) -> TreeNode:
        # write code here
        if pRoot is None:
            return
        pRoot.left, pRoot.right = pRoot.right, pRoot.left
        self.Mirror(pRoot.left)
        self.Mirror(pRoot.right)
        return pRoot


发表于 2022-07-19 15:47:28 回复(0)
Python 3
东方佑头像 东方佑 
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param pRoot TreeNode类 
# @return TreeNode类
#
class Solution:
    def Mirror(self , pRoot: TreeNode) -> TreeNode:
        # write code here
        if not pRoot:
            return pRoot

        return self.jiaohuan(pRoot)
    def jiaohuan(self,root):
        
        root.left,root.right= root.right,root.left
        if root.left:
            self.jiaohuan(root.left)
        
        if root.right:
            self.jiaohuan(root.right)
        return root
        

发表于 2022-07-19 15:28:58 回复(0)
Python 3
lun__头像 lun__ 
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param pRoot TreeNode类 
# @return TreeNode类
#
class Solution:
    def Mirror(self , root: TreeNode) -> TreeNode:
        # write code here
        ## 这里的镜像就相当于反转二叉树 
        if not root: 
            return root
        
        root.left, root.right = root.right, root.left ## 反转左右
        if root.left:
            self.Mirror(root.left)                   ## 进行递归 
        if root.right: 
            self.Mirror(root.right) 
        
        return root 

        
    
    def Mirror(self , root: TreeNode) -> TreeNode:
        ### 用stack来完成反转（前序遍历的迭代法）
        '''
        1. 判断空root 
        2. 定义需要的数据结构，这里使用数组来作为栈stack 
        3. 将树结构压入定义的数据结构中 （将root压入append到stack中）
        4. 弹出当前节点cur，然后对cur的相关信息进行操作
            4.1 层序遍历：res.append(cur.val) 
            4.2 翻转（镜像）：cur.left, cur.right = cur.right, cur.left 
            等 
        5. 判断 cur.left 和 cur.right 是否为空，
            是空：结束了本次循环
            否：继续进行入栈操作append() 和出栈操作pop() 
        6. 根据需要的数据结构，返回对应的情况 （有的需要列表，有的需要返回root)
        '''
        if not root:
            return root 
        
        stack = [] 
        stack.append(root)
        
        while stack:
            cur = stack.pop()  ## 书写方式和层序遍历差不多，
            cur.left, cur.right = cur.right, cur.left 
            
            if cur.left: 
                stack.append(cur.left) 
            
            if cur.right: 
                stack.append(cur.right) 
                
        return root 
    
    
    def Mirror(self , root: TreeNode) -> TreeNode: 
        ## 使用层序遍历的方法完成反转 
        if not root: 
            return root 
        
        from collections import deque 
        que = deque([root])
        
        while que: 
            size = len(que) 
            res = [] 
            for _ in range(size):
                cur = que.popleft() 
                cur.left, cur.right = cur.right, cur.left 
                
                if cur.left: 
                    que.append(cur.left) 
                if cur.right: 
                    que.append(cur.right) 
        return root 
    
    def Mirror(self , root: TreeNode) -> TreeNode: 
        ## 层序遍历 --》 数组 --》二叉树 
        ## 这个无法完全实现，但是通过数组生成二叉树的方法值得记住 
        results = [] 
        if not root: 
            return root 
        
        from collections import deque 
        que = deque([root]) 
        
        while que: 
            size = len(que) 
            res = [] 
            for _ in range(size): 
                cur = que.popleft() 
                res.append(cur.val) 
                
                if cur.left: 
                    que.append(cur.left) 
                    
                if cur.right: 
                    que.append(cur.right) 
                    
            results.append(res) 
        
        results_reverse = [] 
        for alist in results: 
            alist.reverse() 
            results_reverse += alist 
        ## print(results_reverse)
        
        return self.generage_TreeNode(results_reverse)
    
    def generage_TreeNode(self, nums):
        ### 无法得到 空置反转的情况 ！！！
        def level(index): 
            if index >= len(nums)&nbs***bsp;nums[index] is None: 
                return None 
            
            root = TreeNode(nums[index]) 
            root.left = level(2*index+1) 
            root.right = level(2*index+2) 
            
            return root 
        return level(0) 

发表于 2022-07-10 10:56:32 回复(1)
Python 3
StevenWqq头像 StevenWqq
BM31，BM32，BM33 均可用类似思路，先做操作，然后分别递归二叉树左右两边 
class Solution:
    def Mirror(self , pRoot: TreeNode) -> TreeNode:
        # write code here
        if not pRoot:
            return pRoot
        temp = pRoot.left
        pRoot.left = pRoot.right
        pRoot.right = temp
        
        pRoot.left = self.Mirror(pRoot.left)
        pRoot.right = self.Mirror(pRoot.right)
        
        return pRoot


发表于 2022-06-19 13:38:07 回复(0)
Python 3
牛客748432956号头像 牛客748432956号
二叉树镜像的解决思路就是每次将二叉树的左右节点交换位置，当左右节点为空时，返回None。
用到python中的技巧为平行赋值。 

class Solution:
    def Mirror(self , pRoot: TreeNode) -> TreeNode:
        # write code here
        if not pRoot: return None
        pRoot.left, pRoot.right = pRoot.right, pRoot.left
        self.Mirror(pRoot.left)
        self.Mirror(pRoot.right)
        return pRoot


发表于 2022-05-22 18:00:42 回复(0)
Python 3
Vivimore头像 Vivimore

递归
时间复杂度：O(n) 空间复杂度：O(n)

class Solution:
    def Mirror(self , root: TreeNode) -> TreeNode:
        if not root:
            return None
        left_node = root.left
        root.left = root.right
        root.right = left_node 
        self.Mirror(root.left)
        self.Mirror(root.right)
        return root
发表于 2022-05-17 09:51:30 回复(0)
Python 3
一只兔子的奇幻之旅头像 一只兔子的奇幻之旅 
class Solution:
    def Mirror(self , pRoot: TreeNode) -> TreeNode:
        self.swap(pRoot)
        return pRoot
    def swap(self,root):
        if root==None:
            return 
        root.left,root.right=root.right,root.left
        self.swap(root.left)
        self.swap(root.right)

发表于 2022-03-28 16:14:26 回复(0)
Python 3
梦幻泡影oO头像 梦幻泡影oO 
class Solution:
    def Mirror(self , pRoot: TreeNode) -> TreeNode:

        def dfs(x):
            if not x: return None
            x.right, x.left = dfs(x.left), dfs(x.right)
            return x

        return dfs(pRoot)
发表于 2022-03-14 15:47:57 回复(0)
Python 3
想起来就做两道（JihongRen）头像 想起来就做两道（JihongRen） 
class Solution:
    def Mirror(self , pRoot: TreeNode) -> TreeNode:
        if pRoot is None:
            return None
        pRoot.left, pRoot.right = pRoot.right, pRoot.left
        self.Mirror(pRoot.left)
        self.Mirror(pRoot.right)
        return pRoot

发表于 2022-03-10 11:41:32 回复(0)
Python 3
Joy_9头像 Joy_9 
class Solution:
    def Mirror(self , pRoot: TreeNode) -> TreeNode:
        # write code here
        if not pRoot:
            return pRoot 
        if pRoot.left and pRoot.right:
            pRoot.left,pRoot.right=pRoot.right,pRoot.left
            self.Mirror(pRoot.left)
            self.Mirror(pRoot.right)
        elif not pRoot.left: 
            pRoot.left,pRoot.right=pRoot.right,pRoot.left
            self.Mirror(pRoot.left)
        elif not pRoot.right: 
            pRoot.left,pRoot.right=pRoot.right,pRoot.left
            self.Mirror(pRoot.right)
        return pRoot

发表于 2022-01-09 03:59:03 回复(0)
Python 3
闲良头像 闲良
class Solution:
    def Mirror(self , pRoot: TreeNode) -> TreeNode:
        # write code here
        if pRoot and (pRoot.left is not None or pRoot.right is not None):
            temp = self.Mirror(pRoot.left)
            pRoot.left = self.Mirror(pRoot.right)
            pRoot.right = temp
        return pRoot
发表于 2022-01-04 21:05:17 回复(0)
Python 3
握着我的抱枕头像 握着我的抱枕

标题 python递归解法

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param pRoot TreeNode类 
# @return TreeNode类
#
class Solution:
    def Mirror(self , pRoot: TreeNode) -> TreeNode:
        # write code here
        if not pRoot:return
        tmp=self.Mirror(pRoot.left)
        pRoot.left=self.Mirror(pRoot.right)
        pRoot.right=tmp
        return pRoot
发表于 2021-11-03 01:54:53 回复(0)
Python 3
三水123头像 三水123 
class Solution:
    def Mirror(self , pRoot ):
        # write code here
        if pRoot:
            l , r = pRoot.left, pRoot.right
            pRoot.left = self.Mirror(r)
            pRoot.right = self.Mirror(l)
        return pRoot

发表于 2021-08-13 14:15:58 回复(0)
Python 3
可恶，被他装到了头像 可恶，被他装到了
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param pRoot TreeNode类 
# @return TreeNode类
#
def exchange(pRoot):
    if pRoot == None:  # 不存在该节点
        return None
    elif pRoot.left == None and pRoot.right == None:  # 没有子节点
        return None
    else:  # 进行交换
        A = pRoot.left
        pRoot.left = pRoot.right
        pRoot.right = A
        exchange(pRoot.left)
        exchange(pRoot.right)
        return None

class Solution:    
    def Mirror(self , pRoot ):
        exchange(pRoot)
        return pRoot
        
        # write code here
发表于 2021-08-10 12:50:23 回复(0)
Python 3
tantantansq头像 tantantansq 
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param pRoot TreeNode类 
# @return TreeNode类
#
class Solution:
    def Mirror(self , pRoot ):
        # write code here
        if pRoot!=None:
            temp=pRoot.left
            pRoot.left=pRoot.right
            pRoot.right=temp
            self.Mirror(pRoot.left)
            self.Mirror(pRoot.right)
        return pRoot
        

发表于 2021-08-08 20:31:14 回复(0)
Python 3
阿司匹林Yo头像 阿司匹林Yo 
class Solution:
    def Mirror(self, pRoot):
        if not pRoot:
            return None
        l, r = pRoot.left, pRoot.right
        pRoot.left = self.Mirror(r)
        pRoot.right = self.Mirror(l)
        return pRoot

发表于 2021-08-04 15:33:13 回复(0)
提交观点

问题信息

树
上传者：牛客301499号
难度：
20条回答 6201浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号